package 数据结构练习.summer;


import java.util.Arrays;

public class day7 {
    /*
    给定两个字符串 s1 和 s2，请编写一个程序，确定其中
    一个字符串的字符重新排列后，能否变成另一个字符串。
    https://leetcode.cn/problems/check-permutation-lcci/
     */
    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1, str2);
    }

    /*
    每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石
    头的重量分别为x 和y，且x <= y。那么粉碎的可能结果如下：
    如果x == y，那么两块石头都会被完全粉碎；
    如果x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
    最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0
    https://leetcode.cn/problems/last-stone-weight
     */
    public int lastStoneWeight(int[] stones) {
        Arrays.sort(stones);
        int index = stones.length - 1;
        int x;
        int y;
        while (index >0) {
            x = 0;
            y = 0;
            Arrays.sort(stones);
            for (int i = index; i >= 0; i--) {
                if (stones[i] > y) {
                    y = stones[i];
                } else if (stones[i] > x) {
                    x = stones[i];
                }
            }
            int temp = y - x;
            if (temp == 0) {
                index -= 2;
                Arrays.copyOf(stones,index+1);
            } else {
                stones[--index] = temp;
                Arrays.copyOf(stones,index+1);
            }
        }
        if (index<0){
            return 0;
        }else{
            return stones[index];
        }
    }

    /*
    //官方解
     public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
        for (int stone : stones) {
            pq.offer(stone);
        }

        while (pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            if (a > b) {
                pq.offer(a - b);
            }
        }
        return pq.isEmpty() ? 0 : pq.poll();
    }
     */
}
